
//632.最小区间
class Solution {
    public:
        vector<int> smallestRange(vector<vector<int>>& nums) {
            int n=nums.size();
            int ansl=0,ansr=INT_MAX;
            
            //优先级队列使用tuple作为基本单位，
            //因为既要存储最小值，还要存储所在的数组，以及在数组的对应下标位置
            priority_queue<tuple<int,int,int> ,vector<tuple<int ,int ,int>> ,greater<>> pq;
            int themax=INT_MIN;  //存储最大值
            //进行下标为0的插入
            for(int i=0;i<n;i++)
            {
                int tmp=nums[i][0];
                if(tmp>themax) themax=tmp;
    
                pq.push({tmp,i,0});
            }
    
            //进行遍历
            while(1)
            {
                //堆顶就是最小值
                auto [a,b,c]=pq.top();  //a表示最小值，b表示最小值所在的数组，c表示所在数组对应的下标
                pq.pop();
                //更新答案
                if(ansr-ansl>themax-a)  
                ansl=a,ansr=themax;
    
                if(c+1==nums[b].size()) break;  //已经没有元素可以继续进行插入了,直接停止
                int next=nums[b][c+1];  //插入下一个元素
                pq.push({next,b,c+1});
    
                themax=max(themax,next);  //下一个位置可能是最大值
            }
            return {ansl,ansr};
        }
    };